{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tutorial on Poincaré Embeddings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook discusses the basic ideas and use-cases for Poincaré embeddings and demonstrates what kind of operations can be done with them. For more comprehensive technical details and results, this [blog post](https://rare-technologies.com/implementing-poincare-embeddings) may be a more appropriate resource."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Concept and use-case\n",
    "\n",
    "Poincaré embeddings are a method to learn vector representations of nodes in a graph. The input data is of the form of a list of relations (edges) between nodes, and the model tries to learn representations such that the vectors for the nodes accurately represent the distances between them.\n",
    "\n",
    "The learnt embeddings capture notions of both _hierarchy_ and _similarity_ - similarity by placing connected nodes close to each other and unconnected nodes far from each other; hierarchy by placing nodes lower in the hierarchy farther from the origin, i.e. with higher norms.\n",
    "\n",
    "The paper uses this model to learn embeddings of nodes in the WordNet noun hierarchy, and evaluates these on 3 tasks - reconstruction, link prediction and lexical entailment, which are described in the section on evaluation. We have compared the results of our Poincaré model implementation on these tasks to other open-source implementations and the results mentioned in the paper.\n",
    "\n",
    "The paper also describes a variant of the Poincaré model to learn embeddings of nodes in a symmetric graph, unlike the WordNet noun hierarchy, which is directed and asymmetric. The datasets used in the paper for this model are scientific collaboration networks, in which the nodes are researchers and an edge represents that the two researchers have co-authored a paper.\n",
    "\n",
    "This variant has not been implemented yet, and is therefore not a part of our tutorial and experiments.\n",
    "\n",
    "\n",
    "### 1.2 Motivation\n",
    "\n",
    "The main innovation here is that these embeddings are learnt in hyperbolic space, as opposed to the commonly used Euclidean space. The reason behind this is that hyperbolic space is more suitable for capturing any hierarchical information inherently present in the graph. Embedding nodes into a Euclidean space while preserving the distance between the nodes usually requires a very high number of dimensions. A simple illustration of this can be seen below - \n",
    " \n",
    " ![Example tree](https://raw.githubusercontent.com/RaRe-Technologies/gensim/poincare_model_keyedvectors/docs/notebooks/poincare/example_tree.png)\n",
    "\n",
    "Here, the positions of nodes represent the positions of their vectors in 2-D euclidean space. Ideally, the distances between the vectors for nodes `(A, D)` should be the same as that between `(D, H)` and as that between `H` and its child nodes. Similarly, all the child nodes of `H` must be equally far away from node `A`. It becomes progressively hard to accurately preserve these distances in Euclidean space as the degree and depth of the tree grows larger. Hierarchical structures may also have cross-connections (effectively a directed graph), making this harder.\n",
    "\n",
    "There is no representation of this simple tree in 2-dimensional Euclidean space which can reflect these distances correctly. This can be solved by adding more dimensions, but this becomes computationally infeasible as the number of required dimensions grows exponentially. \n",
    "Hyperbolic space is a metric space in which distances aren't straight lines - they are curves, and this allows such tree-like hierarchical structures to have a representation that captures the distances more accurately even in low dimensions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Training the embedding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/home/jayant/projects/gensim\n"
     ]
    }
   ],
   "source": [
    "% cd ../.."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext autoreload   \n",
    "%autoreload 2\n",
    "\n",
    "import os\n",
    "import logging\n",
    "import numpy as np\n",
    "\n",
    "from gensim.models.poincare import PoincareModel, PoincareKeyedVectors, PoincareRelations\n",
    "\n",
    "logging.basicConfig(level=logging.INFO)\n",
    "\n",
    "poincare_directory = os.path.join(os.getcwd(), 'docs', 'notebooks', 'poincare')\n",
    "data_directory = os.path.join(poincare_directory, 'data')\n",
    "wordnet_mammal_file = os.path.join(data_directory, 'wordnet_mammal_hypernyms.tsv')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The model can be initialized using an iterable of relations, where a relation is simply a pair of nodes - "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:gensim.models.poincare:Loading relations from train data..\n",
      "INFO:gensim.models.poincare:Loaded 2 relations from train data, 3 nodes\n"
     ]
    }
   ],
   "source": [
    "model = PoincareModel(train_data=[('node.1', 'node.2'), ('node.2', 'node.3')])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The model can also be initialized from a csv-like file containing one relation per line. The module provides a convenience class `PoincareRelations` to do so."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:gensim.models.poincare:Loading relations from train data..\n",
      "INFO:gensim.models.poincare:Loaded 7724 relations from train data, 1182 unique terms\n"
     ]
    }
   ],
   "source": [
    "relations = PoincareRelations(file_path=wordnet_mammal_file, delimiter='\\t')\n",
    "model = PoincareModel(train_data=relations)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the above only initializes the model and does not begin training. To train the model - "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:gensim.models.poincare:Loading relations from train data..\n",
      "INFO:gensim.models.poincare:Loaded 7724 relations from train data, 1182 unique terms\n",
      "INFO:gensim.models.poincare:training model of size 2 with 1 workers on 7724 relations for 1 epochs and 0 burn-in epochs, using lr=0.10000 burn-in lr=0.01000 negative=10\n",
      "INFO:gensim.models.poincare:Starting training (1 epochs)----------------------------------------\n",
      "INFO:gensim.models.poincare:Training on epoch 1, examples #4990-#5000, loss: 23.57\n",
      "INFO:gensim.models.poincare:Time taken for 5000 examples: 0.47 s, 10562.18 examples / s\n",
      "INFO:gensim.models.poincare:Training finished\n"
     ]
    }
   ],
   "source": [
    "model = PoincareModel(train_data=relations, size=2, burn_in=0)\n",
    "model.train(epochs=1, print_every=500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The same model can be trained further on more epochs in case the user decides that the model hasn't converged yet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:gensim.models.poincare:training model of size 2 with 1 workers on 7724 relations for 1 epochs and 0 burn-in epochs, using lr=0.10000 burn-in lr=0.01000 negative=10\n",
      "INFO:gensim.models.poincare:Starting training (1 epochs)----------------------------------------\n",
      "INFO:gensim.models.poincare:Training on epoch 1, examples #4990-#5000, loss: 21.98\n",
      "INFO:gensim.models.poincare:Time taken for 5000 examples: 0.48 s, 10442.40 examples / s\n",
      "INFO:gensim.models.poincare:Training finished\n"
     ]
    }
   ],
   "source": [
    "model.train(epochs=1, print_every=500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The model can be saved and loaded using two different methods - "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:gensim.utils:saving PoincareModel object under /tmp/test_model, separately None\n",
      "INFO:gensim.utils:saved /tmp/test_model\n",
      "INFO:gensim.utils:loading PoincareModel object from /tmp/test_model\n",
      "INFO:gensim.utils:loading kv recursively from /tmp/test_model.kv.* with mmap=None\n",
      "INFO:gensim.utils:loaded /tmp/test_model\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<gensim.models.poincare.PoincareModel at 0x7f82ec108668>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Saves the entire PoincareModel instance, the loaded model can be trained further\n",
    "model.save('/tmp/test_model')\n",
    "PoincareModel.load('/tmp/test_model')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:gensim.models.keyedvectors:storing 3x50 projection weights into /tmp/test_vectors\n",
      "INFO:gensim.models.keyedvectors:loading projection weights from /tmp/test_vectors\n",
      "INFO:gensim.models.keyedvectors:loaded (3, 50) matrix from /tmp/test_vectors\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<gensim.models.poincare.PoincareKeyedVectors at 0x7f82d03c6588>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Saves only the vectors from the PoincareModel instance, in the commonly used word2vec format\n",
    "model.kv.save_word2vec_format('/tmp/test_vectors')\n",
    "PoincareKeyedVectors.load_word2vec_format('/tmp/test_vectors')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. What the embedding can be used for"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:gensim.utils:loading PoincareModel object from /home/jayant/projects/gensim/docs/notebooks/poincare/models/gensim_model_batch_size_10_burn_in_0_epochs_50_neg_20_dim_50\n",
      "INFO:gensim.utils:loading kv recursively from /home/jayant/projects/gensim/docs/notebooks/poincare/models/gensim_model_batch_size_10_burn_in_0_epochs_50_neg_20_dim_50.kv.* with mmap=None\n",
      "INFO:gensim.utils:loaded /home/jayant/projects/gensim/docs/notebooks/poincare/models/gensim_model_batch_size_10_burn_in_0_epochs_50_neg_20_dim_50\n"
     ]
    }
   ],
   "source": [
    "# Load an example model\n",
    "models_directory = os.path.join(poincare_directory, 'models')\n",
    "test_model_path = os.path.join(models_directory, 'gensim_model_batch_size_10_burn_in_0_epochs_50_neg_20_dim_50')\n",
    "model = PoincareModel.load(test_model_path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The learnt representations can be used to perform various kinds of useful operations. This section is split into two - some simple operations that are directly mentioned in the paper, as well as some experimental operations that are hinted at, and might require more work to refine.\n",
    "\n",
    "The models that are used in this section have been trained on the transitive closure of the WordNet hypernym graph. The transitive closure is the list of all the direct and indirect hypernyms in the WordNet graph. An example of a direct hypernym is `(seat.n.03, furniture.n.01)` while an example of an indirect hypernym is `(seat.n.03, physical_entity.n.01)`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Simple operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All the following operations are based simply on the notion of distance between two nodes in hyperbolic space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.9232418343441235"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Distance between any two nodes\n",
    "model.kv.distance('plant.n.02', 'tree.n.01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.5111423377921103"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model.kv.distance('plant.n.02', 'animal.n.01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('phenomenon.n.01', 2.0296901412261614),\n",
       " ('natural_phenomenon.n.01', 2.1052921648852934),\n",
       " ('physical_phenomenon.n.01', 2.1084626073820045),\n",
       " ('photoelectricity.n.01', 2.4527217652991005),\n",
       " ('piezoelectricity.n.01', 2.4687111939575397),\n",
       " ('galvanism.n.01', 2.9496409087300357),\n",
       " ('cloud.n.02', 3.164090455102602),\n",
       " ('electrical_phenomenon.n.01', 3.2563741920630225),\n",
       " ('pressure.n.01', 3.3063009504377368),\n",
       " ('atmospheric_phenomenon.n.01', 3.313970950348909)]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Nodes most similar to a given input node\n",
    "model.kv.most_similar('electricity.n.01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('male.n.02', 1.725430794111438),\n",
       " ('physical_entity.n.01', 3.5532684790327624),\n",
       " ('whole.n.02', 3.5663516391532815),\n",
       " ('object.n.01', 3.5885342299888077),\n",
       " ('adult.n.01', 3.6422291495399124),\n",
       " ('organism.n.01', 4.096498630105297),\n",
       " ('causal_agent.n.01', 4.127447093914292),\n",
       " ('living_thing.n.01', 4.198756842588067),\n",
       " ('person.n.01', 4.371831459784078),\n",
       " ('lawyer.n.01', 4.581830548066727)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model.kv.most_similar('man.n.01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['domestic_animal.n.01',\n",
       " 'canine.n.02',\n",
       " 'terrier.n.01',\n",
       " 'hunting_dog.n.01',\n",
       " 'hound.n.01']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Nodes closer to node 1 than node 2 is from node 1\n",
    "model.kv.nodes_closer_than('dog.n.01', 'carnivore.n.01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Rank of distance of node 2 from node 1 in relation to distances of all nodes from node 1\n",
    "model.kv.rank('dog.n.01', 'carnivore.n.01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.24618276804\n",
      "[ 0.20492232  0.21622492  0.22568267  0.20813361  0.26086168]\n"
     ]
    }
   ],
   "source": [
    "# Finding Poincare distance between input vectors\n",
    "vector_1 = np.random.uniform(size=(100,))\n",
    "vector_2 = np.random.uniform(size=(100,))\n",
    "vectors_multiple = np.random.uniform(size=(5, 100))\n",
    "\n",
    "# Distance between vector_1 and vector_2\n",
    "print(PoincareKeyedVectors.vector_distance(vector_1, vector_2))\n",
    "# Distance between vector_1 and each vector in vectors_multiple\n",
    "print(PoincareKeyedVectors.vector_distance_batch(vector_1, vectors_multiple))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Experimental operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These operations are based on the notion that the norm of a vector represents its hierarchical position. Leaf nodes typically tend to have the highest norms, and as we move up the hierarchy, the norm decreases, with the root node being close to the center (or origin)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'writer.n.01'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Closest child node\n",
    "model.kv.closest_child('person.n.01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'causal_agent.n.01'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Closest parent node\n",
    "model.kv.closest_parent('person.n.01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.940798238231\n",
      "0.967868985302\n"
     ]
    }
   ],
   "source": [
    "# Position in hierarchy - lower values represent that the node is higher in the hierarchy\n",
    "print(model.kv.norm('person.n.01'))\n",
    "print(model.kv.norm('teacher.n.01'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.027070747071\n"
     ]
    }
   ],
   "source": [
    "# Difference in hierarchy between the first node and the second node\n",
    "# Positive values indicate the first node is higher in the hierarchy\n",
    "print(model.kv.difference_in_hierarchy('person.n.01', 'teacher.n.01'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['carnivore.n.01',\n",
       " 'dog.n.01',\n",
       " 'hunting_dog.n.01',\n",
       " 'terrier.n.01',\n",
       " 'sporting_dog.n.01']"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# One possible descendant chain\n",
    "model.kv.descendants('mammal.n.01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['canine.n.02',\n",
       " 'domestic_animal.n.01',\n",
       " 'placental.n.01',\n",
       " 'ungulate.n.01',\n",
       " 'chordate.n.01',\n",
       " 'animal.n.01',\n",
       " 'physical_entity.n.01']"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# One possible ancestor chain\n",
    "model.kv.ancestors('dog.n.01')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the chains are not symmetric - while descending to the closest child recursively, starting with `mammal`, the closest child of `carnivore` is `dog`, however, while ascending from `dog` to the closest parent, the closest parent to `dog` is `canine`. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is despite the fact that Poincaré distance is symmetric (like any distance in a metric space). The asymmetry stems from the fact that even if node `Y` is the closest node to node `X` amongst all nodes with a higher norm (lower in the hierarchy) than `X`, node `X` may not be the closest node to node `Y` amongst all the nodes with a lower norm (higher in the hierarchy) than `Y`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Useful Links"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. [Original paper by Facebook AI Research](https://arxiv.org/pdf/1705.08039)\n",
    "2. [Blog post describing technical challenges in implementation](https://rare-technologies.com/implementing-poincare-embeddings)\n",
    "3. [Detailed evaluation notebook to reproduce results](https://github.com/RaRe-Technologies/gensim/blob/develop/docs/notebooks/Poincare%20Evaluation.ipynb)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
